The present invention relates to a method and apparatus for rendering a halftone image from a grayscale image. More particularly, the present invention relates to a method and apparatus for coalescing grayscale intensity values within selected neighborhoods before transforming the grayscale image into a halftone image.
Continuous tone images or grayscale images which are made up of a series of regularly spaced tones ranging from white to black through intermediate shades of gray must often be rendered as a binary image or halftone image in a wide range of display devices such as printers, facsimile machines, lithography, liquid crystal displays and plasma panels to name a few. A display processor is frequently used to convert a grayscale image to a binary or halftone image. The halftone image is an arrangement of binary picture elements which provides the illusion of grayscale or continuous tone images. The algorithm or process performed by the display processor is frequently referred to as digital halftoning.
Some of these halftoning techniques are described in "Digital Halftoning" by R. Ulichney, MIT Press, Cambridge, Mass. (1987) incorporated herein by reference. These halftoning algorithms are often classified into point and neighborhood algorithms based on the number of points or pixels in the grayscale image that are utilized in determining each pixel in the binary or halftone image. The generic form of point algorithm a grayscale or continuous tone, discrete space image J[n] is compared with a threshold to determine an output halftone image I[n].
One such point algorithm is disclosed in U.S. Pat. No. 5,111,310 to Parker et al. entitled METHOD AND APPARATUS FOR HALFTONE RENDERING OF A GRAYSCALE IMAGE USING A BLUE NOISE MASK. The Parker patent discloses a method whereby the grayscale image is compared on a pixel-by-pixel basis against a blue noise mask to render a halftone image. Point algorithms are generally fast relative to neighborhooding algorithms. However, point algorithms tend to suffer from artifact problems such as periodic artifacts and false contours.
In contrast, to point algorithms neighborhood algorithms require more than one point from the grayscale image to determine each pixel of the halftone image. A popular neighborhood algorithm is an error diffusion algorithm. General form of the error diffusion algorithm the output binary image I[n] having values of 0 or 1 are compared with the original grayscale or continuous tone image J[n]. The difference between this input and output value is referred to as the "error" for location n. An error signal representing past errors is passed through an error filter, E[n], to produce a correction factor which is added to future input values.
One form of error diffusion is disclosed in U.S. Pat. No. 5,201,013 to Kumagi entitled DITHER PROCESSING METHOD. Error diffusion methods in general have several shortcomings. One shortcoming is the presence of correlated artifacts in many of the gray level patterns. A second shortcoming is directional hysteresis due to the raster order of processing which is most apparent in very light and dark patterns. Additionally, error diffusion algorithms tend to have transient behavior near edges or boundaries. These problems are discussed in more detail and illustrated in "Digital Halftoning" by R Ulichney.
There is an ever present need for halftoning techniques that minimize artifacts and undesired patterns in the binary or halftone output. In addition, these techniques should be capable of executing relatively fast and have relatively modest processor and memory requirements for the image preprocessor. In general, the greater the processor and memory requirements, the greater the cost of the preprocessor.
In addition, a halftoning technique should be capable of compensating for the darkening of the output image due to broadening and overlap of adjacent black pixels which darkens the image, frequently referred to as "dot gain". Because of this dot overlap phenomenon there is little change in reflectance or perceivable tone changes as more pixels are added to high density regions. Therefore, the halftoning technique should be able to compensate for this nonlinearity in tone where pixel density is large.
A related problem occurs as a result of nonlinearity in the reflectance or tone changes for very light tone which must be compensated for in the halftoning algorithm. This nonlinearity occurs because the first level of tint or lightest tone produces the appearance of being much greater than each of the subsequent levels of increasing tone, for example, algorithms that make use of a 16 by 16 halftone grid for displaying 256 levels of gray values. An increasing number of pixels are selectively turned on within the grid to achieve increasing levels of gray. However, the minimum tint level with just one pixel of the 64 pixels turned on is a very noticeable level of tint. Moreover, this first level of tint appears to be greater than each subsequent level of increasing tint. Therefore, the halftoning technique should be capable of compensating for this minimum tint level so that the first tint level is not as extreme.
The halftoning technique should also provide a halftone output image that when transferred to printing plate provides good lithographic properties. Plate making for offset printing requires large and well formed pixels in the output image. Therefore, the halftoning algorithm should form pixels that are well suited to the plate making process.
Finally, output devices such as printers tend to have problems that effect the output image that is the result of the printer mechanism and not the form of halftoning algorithm. An example is gear noise, which is the result of nonuniform line spacing between adjacent rows or columns in the output binary image. This nonuniform line spacing is the result of imperfections in the mechanism used to move the paper past a scanner or print head which puts toner on the paper. Gear noise is a greater problem as the resolution of the printing device becomes higher or better. For example, a 1200 dot per inch print engine places rows or columns of pixels 10 at a separation of 1/1200 of an inch as compared to a 300 dot per inch print engine which places rows and columns of pixels at a separation of 1/300 of an inch. For the same error in movement of paper through each of these print engines the percentage of error relative to line spacing is much greater for the higher resolution 1200 dot per inch print engine. Previously used high resolution printers have made use of much more costly mechanisms for moving paper past the print engine. However, this adds significantly to the cost of the printing or output device. Therefore, there is a present need for printing devices which exhibit minimal gear noise that utilize relatively low cost paper transfer mechanisms.